package algorithm.leetcode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 给定一个无重复元素的数组 candidates 和一个目标数 target ，
 找出 candidates 中所有可以使数字和为 target 的组合。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/4
 */
public class Question39 {

    public static void main(String[] args) {
        Question39 question = new Question39();
        int[] nums = {2,3,7};
        List<List<Integer>> list = question.combinationSum(nums, 7);
        System.out.println(list);
    }


    private List<List<Integer>> res = new ArrayList<>(10);

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>(10);
        Arrays.sort(candidates);
        backtrack(path, candidates, target, 0, 0);
        return res;
    }

    private void backtrack(List<Integer> path, int[] candidates, int target, int sum, int begin) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < candidates.length; i++) {
            int r = candidates[i] + sum;
            if (r <= target) {
                path.add(candidates[i]);
                backtrack(path, candidates, target, r, i);
                path.remove(path.size() - 1);
            }else {
                break;
            }
        }
    }
}
